#DataStructure #DataStructure-Heap #DataStructure-Priority_Queue

관련 문제: 506. Relative Ranks

1. 우선순위 큐?

위키-우선순위 큐
=> 우선순위가 높은 원소가 낮은 원소보다 먼저 처리될 수 있도록 구성된 큐

Queue는 FIFO(First In First Out, 선입 선출)이다. 이것을 Any In Priority High First Out으로 생각하면 될 것 같다.

힙과 거의 동일시 되는 분위기이고, 우선순위 큐나 힙이나 최대(최고 우선순위), 최소(최저 우선순위)를 다룬다는 것마저 비슷하다. 그리고 구현에 있어서 힙만큼 우선순위 큐를 구현하기 최적의 것이 없다지만, 우선순위 큐와 힙의 차이점이라면 힙은 완전 이진 트리로 구현될 필요도, 트리로 구현될 필요도 없다. 그것이 차이 인 것 같고, 우선순위 큐를 이용해서 정렬을 하지도 않는다는 점에서 구분하지 않나 싶다.

2. 우선순위 큐 만들기

우선순위 큐를 여러가지 방법으로 만들 수 있지만, 힙만큼 우선순위 큐를 구현하기 좋은 것도 없다.

우선순위 큐를 생성하는 방법은 힙 생성하는 방법과 같고, 우선순위 큐에서 원소를 pull하는 방법(Queue이기 때문에 (Priority Highiest) First Out으로 한번에 하나의 원소만 빼는 것이 특징이다.)도 힙에서 원소 삭제하기 방법과 같다.

Heap 포스트를 참고하도록 하자.
힙을 이용한 우선순위 큐의 구현을 보고 싶다면 506. Relative Ranks을 보자.